#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int, int> hash;
        for (int i = 0; i < n; i++) hash[arr[i]]++;
        priority_queue<int, vector<int>, less<int>> heap;
        for (auto pair : hash) heap.push(pair.second);
        int len = 0, trys = 0;
        while (len < n / 2)
        {
            len += heap.top(); heap.pop();
            ++trys;
        }
        return trys;
    }
};